package com.jack.leetcode.eachproblem_2020;

import java.util.ArrayList;
import java.util.List;

public class 将数组拆分成斐波那契数列 {

    public List<Integer> splitIntoFibonacci(String S) {
        List<Integer> result = new ArrayList<>();
        backTrack(result, S, 0);
        return result;
    }

    private boolean backTrack(List<Integer> result, String S, int index){
        if(index == S.length() && result.size() >= 3){
            return true;
        }
        for(int i = index;i < S.length();i++){
            if(S.charAt(index) == '0' && i >= index){
                break;
            }
            long num = Long.valueOf(S.substring(index, i + 1));
            if(num > Integer.MAX_VALUE){
                break;
            }
            int size = result.size();
            if(size >= 2 && num > result.get(size - 1) + result.get(size - 2)){
                break;
            }
            if(size <= 1 || num == result.get(size - 1) + result.get(size - 2)){
                result.add((int)num);
                if(backTrack(result, S, i + 1)){
                    return true;
                }
                result.remove(result.size() - 1);
            }
        }
        return false;
    }
}
